package hot_100;

public class 数组中的第K个最大元素 {
    public static void main(String[] args) {
        int[] nums = {2, 1};
        int largest = findKthLargest(nums, 2);
        System.out.println(largest);
    }

    static int[] numss;

    public static int findKthLargest(int[] nums, int k) {
        numss = nums;
        return quick_sort(0, nums.length - 1, nums.length - k);
    }

    public static int quick_sort(int l, int r, int k) {
        if (l == r)
            return numss[l];
        int num = numss[l];
        int ll = l + 1;
        int rr = r;
        while (rr > ll) {
            while (rr > ll && numss[rr] >= num) {
                if (numss[rr] == num) {
                    rr--;
                    break;
                }
                rr--;
            }
            while (rr > ll && numss[ll] <= num) {
                if (numss[ll] == num) {
                    ll++;
                    break;
                }
                ll++;
            }
            if (rr > ll) {
                int temp = numss[ll];
                numss[ll] = numss[rr];
                numss[rr] = temp;
            }
        }
        numss[l] = num;
        if (ll < k)
            return quick_sort(ll + 1, r, k);
        return quick_sort(l, ll, k);
    }
}
